The present invention relates to channel equalisers and, in particular, channel equalisers for multi-user Code Division Multiple Access (CDMA) receivers.
In the proposed European Universal Terrestrial Radio Access (UTRA) third generation cellular implementation of Universal Mobile Telecommunication Service (UMTS) there is a problem in the downlink direction (base station to subscriber) relating to the computation load of the terminals when the channels are highly dispersive. In the Time Division Duplex (TDD) mode the spreading factor is only 16 i.e. one channel information bit corresponds to 16 chips and performance is at a premium. Channel effects such as dispersion render the 16 user codes non-orthogonal and mutual interference can be high, reducing system capacity. Current proposals are to use a common front-end equaliser for the terminals which re-whitens the channel impulse response and remove this mutual interference. It is presently envisaged that the TDD mode will be employed for data and voice since, in the unpaired spectrum, it is better suited to highly asymmetric bandwidth (e.g. 15:1) applications. FIG. 1 shows the stages involved in the transmission and reception of radio signals from a digital pulse shaper at a transmitter to a receiver.
The equaliser (filter) conventionally proposed for CDMA down links is an Finite Impulse Response (FIR) digital filter which operates at baseband in the receiver. The channel dispersion may extend up to 20 xcexc s for the worst vehicular channels (IMT-2000 selection criteria documents), which is equivalent to 83 channel symbols at the UTRA chipping rate of 4.096 MHz. The chipping rate refers to the lowest symbol rate of the channel. Thus this filter may have a large number of taps and the work load is correspondingly high, being of the order of 4.096xc3x9783=340 MIPS. This may be too high a work load for a portable terminal under current technologies, so methods of reducing the load of the filter are necessary to reduce power consumption and thus conserve battery power.
There are other considerations relating to the statistical stability of the tap values if the filter has too many taps. Because the channel impulse response is estimated from a finite duration training sequence, the filter weights are determined with some random error components whose effect increases in proportion to the number of taps estimated, Thus it is always desirable to reduce the number of taps in the filter yet not compromise equalisation performance. Thus it is often proposed that the channel data can be windowed and the tap data in the window be transformed into eigenspace via the Karhunen Loeve transformation though this also has a high computational cost.
The digital processing load of a receiver equaliser has two parts: firstly the low-level digital filtering function work load at the chip rate and secondly the work load of the high-level real-time filter design algorithm which typically involves matrix manipulations which incur a heavy memory and instruction count. Efficient minimisation of the first generally involves an increase of the second component.
The present invention seeks to provide a channel equaliser for multi-user CDMA receivers that provides a reduced computational load than is presently known.
The invention further seeks to provide an efficient means of designing an FIR digital equaliser filter which has a large time span, equal at least to the channel dispersion, but with only a small number of active tap weights.
STATEMENT OF THE INVENTION
In accordance with the invention, there is provided an algorithm whereby a digital filter can be adapted to conform to some recognised optimality criterion which is known to lead to a minimum mutual interference situation. The algorithm selects a sparse set of delay line taps in an optimal fashion and accordingly determines a reduced work load, The algorithm has two variants which lead to the same solution. One is a simple search procedure and the second is a numerical algorithm which has a smaller computation load. In accordance with one aspect, the method is constrained to a minimum output finite impulse response (FIR) digital filter power condition.
In accordance with a second aspect of the invention, there is provided a method comprising the determination of a sparse FIR filter which has a relatively small number of active weighting coefficients Ntap which relates to the potential number of taps and Nchan which is the product of the CDMA chipping rate and the span of the dispersion of the channel.
In accordance with a third aspect of the invention, there is provided a method of determining the filter taps for a digital filter on a non-ideal channel comprising the steps of:
obtaining impulse response values {h0, h1, h2 . . . hn} to create a channel response matrix H;
applying Givens"" rotation algorithm to matrix H comprising the sub-steps of:
(i) using a sequence of Nxe2x88x921 2xc3x972 rotation operations the top row is made zero to the right of the first element;
(ii) copying and applying identical sequences of rotations in the same order to the second and subsequent rows; and
(iii) permuting the matrix to achieve the best value for the second diagonal element;
(iv) repeating steps i) and ii) for the second row with a corresponding reduction to zero of the elements of each row to the right of the diagonal;
(v) repeating steps iii) and iv) for subsequent rows up to a limit:
whereby to produce a lower triangular matrix L;
inverting L; and
extracting the leading column, and mapping the element locations in W back through an inverse pivot map;
whereby to relate the weights to the permuted row number, wherein, for each element of the leading column the mapped values of the permuted row number corresponds to the number of the selected tap to be employed of the filter and the elements of the leading column of the inverted matrix correspond to the desired weights taps of the filter.
A second method describes the operation of an algorithm which selects the best subset of coefficients to retain and the complementary set which can be discarded. A low-cost sequential pivoting QR triangular decomposition of the channel impulse response matrix is used for this function (QR is the notation employed for the product of an orthogonal matrix and an upper triangular matrix). This algorithm sequentially increases the number of taps, selecting the best new ones to use out of the total available which minimises some error measure in the resulting sparse equalisation. This QR algorithm is numerically robust, has little error propagation, and will operate with fixed point arithmetic. The total work load is proportional to Nchanxc2x7Ntap2 
In accordance with a further aspect of the invention there is provided a FIR filter comprising a semiconductor chip (ASIC or FPGA chip) programmed to operate in accordance with the algorithm.
In accordance with another aspect of the invention, there is provided, in a filter for a non-ideal channel having a delay line with N floating tap connections and variable coefficient values, a method of determining the filter tap characteristics comprising the steps of: searching for a pivot filter tap; connecting said pivot tap to a first tap of the delay line; replacing the pivot filter tap with a variable filter tap and connecting the pivot to one of the Nxe2x88x921 locations remaining; and, at each pivot location optimising the first co-efficient value according to a selected optimality criterion; wherein the search is terminated when the best location for the pivot tap has been determined; determining a subset of optimal locations; determining filter tap values for said optimal locations wherein, for each sequential step of the process, Mxe2x88x921 variable coefficients and one pivot are provided; and the variable coefficients are connected to those delay line taps which were determined to be optimal in step Mxe2x88x921; wherein the mth pivot is scanned through the unused Nxe2x88x92Mxe2x88x921 delay line taps remaining and the best one is found as before. and best location of the movable coefficient is decided according to a minimum residual power criterion.
In accordance with another aspect of the invention, there is provided a digital filter having a plurality of filter taps wherein the filter is operable such that a sparse sub-set of filter taps may be determined according to the following steps:
obtaining impulse response values {h0, h1, h2 . . . hN} to create a channel response matrix H;
applying Givens"" rotation algorithm to matrix H comprising the sub-steps of:
i) using a sequence of Nxe2x88x921 2xc3x972 rotation operations the top row is made zero to the right of the first element;
ii) copying and applying identical sequences of rotations in the same order to the second and subsequent rows; and
iii) permuting the matrix to achieve the best value for the second diagonal element;
iv) repeating steps i) and ii) for the second row with a corresponding reduction to zero of the elements of each row to the right of the diagonal;
v) repeating steps iii) and iv) for subsequent rows up to a limit;
whereby to produce a lower triangular matrix L;
inverting L; and
extracting the leading column, and mapping the element locations in W back through an inverse pivot map
whereby for each element of the leading column the mapped values of the permuted row number corresponds to the number of the selected tap to be employed of the filter and the elements of the leading column of the inverted matrix correspond to the desired weights taps of the filter.
In accordance with another aspect of the invention, there is provided a filter for a non-deal channel having a delay line with N stages and M connections with variable coefficient values, where M less than N , the filter being operable to determine the filter tap characteristics comprising the method steps of:
connecting a pivot tap to a first tap of the delay line replacing the pivot filter tap with a variable filter tap and connecting the pivot to one of the Nxe2x88x921 locations remaining; and,
at each pivot location optimising the first co-efficient value according to a selected optimality criterion;
wherein the search is terminated when the best location for the pivot tap has been determined;
determining a subset of optimal locations;
determining filter tap values for said optimal locations wherein, for each sequential step of the process, Mxe2x88x921 variable coefficients and one pivot are provided;
and the variable coefficients are connected to those delay line taps which were determined to be optimal in step Mxe2x88x921;
wherein the mth pivot is scanned through the unused Nxe2x88x92Mxe2x88x921 delay line taps remaining and the best one is found as before. and best location of the movable coefficient is decided according to a minimum residual power criterion.
Conveniently, the optimality criterion is output power and best location of the movable coefficient is decided according to a minimum residual power criterion.
The invention thus provides a method for reducing the computation load of digital equalisers for CDMA cellular wireless receivers, particularly in the European UTRA implementation of third generation cellular radio. For downlink transmission in synchronous TDD mode the handsets/terminals will use a common equaliser which whitens the channel impulse response and thereby removes mutual interference between users. This technique thus minimises the number of taps in this channel equaliser and hence the computation load of such digital equalisers.